class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        size = len(s)

        # dp[i][j] = 令字符串[i,j]变为回文串需要删除的字符数
        dp = [[[0] * 26 for _ in range(size)] for _ in range(size)]

        for length in range(2, size + 1):
            for i in range(size - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    a = ord(s[i]) - 97
                    for k in range(26):
                        dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j - 1][k])
                        if k != a:
                            dp[i][j][a] = max(dp[i][j][a], dp[i + 1][j - 1][k] + 1)
                            # print(i + 1, j - 1, k, "->", i, j, a, "=", dp[i][j][a])
                    # print(i, j, a, ":", dp[i][j][a])
                else:
                    for k in range(26):
                        dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k])

        return max(dp[0][-1]) * 2


if __name__ == "__main__":
    print(Solution().longestPalindromeSubseq("bbabab"))  # 4
    print(Solution().longestPalindromeSubseq("dcbccacdb"))  # 4
